package one;

import java.util.ArrayList;
import java.util.List;

/**
 * N 叉树的前序遍历
 * 时间复杂度：O(n)
 * 思路：深度优先，递归
 */
public class Preorder {
    private List<Integer> ans = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        find(root);
        return ans;
    }
    private void find(Node root){
        if (root == null) return;
        ans.add(root.val);
        for (Node child : root.children){
            find(child);
        }
    }
}
class Node{
    int val;
    List<Node> children;
    public Node(){}
    public Node(int val){
        this.val = val;
    }
    public Node(int val, List<Node> children){
        this.children = children;
    }
}
